package com.zhugang.week13.hash;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * @program algorithms
 * @description: CheckPermutation
 * @author: chanzhugang
 * @create: 2022/12/04 22:24
 */
public class CheckPermutation {

    /**
     * 面试题01.02 判定是否互为字符重排
     * https://leetcode.cn/problems/check-permutation-lcci/
     *
     * @param s1
     * @param s2
     * @return
     */
    public boolean CheckPermutation(String s1, String s2) {
        /**
         * 思路：s1存哈希表；s2是否在哈希表，对应count-1；检查s1是否为空
         */
        Map<Character, Integer> map = new HashMap<>();
        for (char c : s1.toCharArray()) {
            // 统计s1词频
            int count = 1;
            if (map.containsKey(c)) {
                count += map.get(c);
            }
            map.put(c, count);
        }

        // s2跟s1匹配
        for (char c : s2.toCharArray()) {
            if (!map.containsKey(c)) {
                return false;
            }
            int count = map.get(c);
            if (count == 0) {
                return false;
            }
            map.put(c, count - 1);
        }
        // 校验s1
        for (char c : s1.toCharArray()) {
            if (map.get(c) != 0) {
                return false;
            }
        }
        return true;
    }


    public boolean CheckPermutation2(String s1, String s2) {
        /**
         * 数组排序，每个元素比较是否相等
         */
        if (s1.length() != s2.length()) {
            return false;
        }
        char[] array1 = s1.toCharArray();
        char[] array2 = s2.toCharArray();
        Arrays.sort(array1);
        Arrays.sort(array2);
        // 记住这些简洁写法
        return Arrays.equals(array1, array2);

        /*for (int i = 0; i < array1.length; i++) {
            if (array1[i] != array2[i]) {
                return false;
            }
        }
        return true;*/
    }


}